home *** CD-ROM | disk | FTP | other *** search
/ Resource Library: Multimedia / Resource Library: Multimedia.iso / sgml / unix / sgmlc / context.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-07-03  |  20.9 KB  |  451 lines
  1. /******************************************************************************/
  2. #include "sgmlincl.h"         /* #INCLUDE statements for SGML parser. */
  3. /******************************************************************************/
  4. #define GI (tags[ts].tetd->etdgi+1)              /* GI of current element. */
  5. #define NEWGI (newetd->etdgi+1)                  /* GI of new tag. */
  6. /******************************************************************************/
  7. #define STATUS (*statuspt)    /* Token status: RCHIT RCMISS RCEND RCREQ RCNREQ*/
  8. #define RCEND    1            /* No more tokens: end element and retry GI. */
  9. #define RCREQ    2            /* Required GI must precede proposed GI. */
  10. #define RCMISS   3            /* GI invalid: not element end; no required GI. */
  11. #define RCHIT    4            /* GI is the one expected next. */
  12. #define RCMEX    5            /* GI invalid: minus exception. */
  13. #define RCHITMEX 6            /* RCMEX with invalid attempted minus exclusion.*/
  14. #define RCPEX    7            /* GI is valid solely because of plus exclusion.*/
  15. #define RCNREQ   8            /* Token is not required; can retry invalid GI. */
  16. #define PEX     -1            /* GI is a plus exception and not a minus. */
  17. #define M      pos[0].g       /* Index of current token in model. */
  18. #define P      pos[0].t       /* Index of current group in pos. */
  19. #define G      pos[P].g       /* Index of current group in model. */
  20. #define T      pos[P].t       /* Index of current token in its group. */
  21. #define H      pos[P].h       /* Hit bits for current group's tokens (1=hit). */
  22. #define GHDR   mod[G]         /* Current group header. */
  23. #define TOKEN  mod[M]         /* Current token. */
  24. #define TTYPE (GET(TOKEN.ttype, TTMASK))  /* Token type of current token. */
  25. #define TOCC  (GET(TOKEN.ttype, TOREP))   /* Occurrence for current token. */
  26. #define GTYPE (GET(GHDR.ttype, TTMASK))   /* Token type of current group. */
  27. #define GOCC  (GET(GHDR.ttype, TOREP))    /* Occurrence for current group. */
  28. #define GNUM  GHDR.tu.tnum                /* Number of tokens in current grp. */
  29. /******************************************************************************/
  30. static long l1;               /* Intermediate variable for hit selector. */
  31. #define TOKENHIT (l1 = 1L<<(T-1), H&l1) /* 1=current token was hit; 0=not*/
  32. /******************************************************************************/
  33. /* CONTEXT: Determine whether a GI is valid in the present structural context.
  34.             Returns RCHIT if valid, RCEND if element has ended, RCREQ if a
  35.             different element is required, and RCMISS if it is totally invalid.
  36.             On entry, pos points to the model token to be tested against the GI.
  37.             TO DO: Save allowed GIs for an error message on an RCMISS.
  38.                    Support a "query" mode (what is allowed now?) by working
  39.                    with a copy of pos.
  40. */
  41. int context(gi, mod, pos, statuspt, mexts)
  42. struct etd *gi;               /* ETD of new GI. */
  43. struct thdr mod[];            /* Model of current open element. */
  44. struct mpos pos[];            /* Position in open element's model. */
  45. UNCH *statuspt;               /* Token status: RCHIT RCMISS RCEND RCREQ RCNREQ*/
  46. int mexts;                    /* >0=stack level of minus grp; -1=plus; 0=none.*/
  47. {
  48.      UNCH toccsv, gtypesv;    /* Save token's TOCC and GTYPE in case grp ends.*/
  49.  
  50.      Tstart = T;              /* Save starting token for AND group testing. */
  51.      while (STATUS!=RCMISS && STATUS!=RCEND) {
  52. #ifndef FINAL
  53.           if (ctrace) tracegi("CONTEXT", gi, mod, pos, (int)Tstart);
  54. #endif
  55.           while (TTYPE==TTOR || TTYPE==TTSEQ || TTYPE==TTAND) {
  56.                pos[P+1].g = M++; pos[++P].t = 1; H = 0;
  57.                Tstart = T;    /* Save starting token for AND group testing. */
  58. #ifndef FINAL
  59.                if (ctrace) tracegi("OPENGRP", gi, mod, pos, (int)Tstart);
  60. #endif
  61.           }
  62.           STATUS = (char)tokenreq(gi, mod, pos);
  63. #ifndef FINAL
  64.           if (ctrace) tracegi("STATUS", gi, mod, pos, (int)Tstart);
  65. #endif
  66.           if (gi==TOKEN.tu.thetd) {     /* Hit in model. */
  67.                STATUS = (char)RCHIT;
  68.                gtypesv = GTYPE; toccsv = TOCC;
  69.                newtoken(mod, pos, statuspt);
  70.                return(mexts<=0 ? RCHIT : (gtypesv==TTOR || BITON(toccsv, TOPT))
  71.                                        ?  RCMEX : RCHITMEX);
  72.           }
  73.           if (mexts==-1) return((int)(STATUS = RCPEX));  /* Hit in plus grp. */
  74.           if (STATUS==RCREQ) {
  75.                STATUS = RCHIT;
  76.                nextetd = TOKEN.tu.thetd;
  77.                newtoken(mod, pos, statuspt);
  78.                return(RCREQ);
  79.           }
  80.           /* else if (STATUS==RCNREQ) */
  81.                if (mexts>0) return(RCMEX);
  82.                newtoken(mod, pos, statuspt);
  83.      }
  84.      return((int)STATUS);
  85. }
  86. /******************************************************************************/
  87. /* ECONTEXT: Determine whether the current element can be ended, or whether
  88.              non-optional tokens remain at the current level or higher.
  89.              Returns 1 if element can be ended, or 0 if tokens remain.
  90.              On entry, STATUS==RCEND if there are no tokens left; if not,
  91.              pos points to the next model token to be tested.
  92.              TO DO: Support a "query" mode (what is required now?) by working
  93.                     with a copy of pos.
  94. */
  95. int econtext(mod, pos, statuspt)
  96. struct thdr mod[];            /* Model of current open element. */
  97. struct mpos pos[];            /* Position in open element's model. */
  98. UNCH *statuspt;               /* Token status: RCHIT RCMISS RCEND RCREQ RCNREQ*/
  99. {
  100.      unsigned next;           /* Position in AND group of next testable token.*/
  101.  
  102.      Tstart = T;
  103. #ifndef FINAL
  104.      if (ctrace) traceend("ECONT", mod, pos, 0, 0, (int)Tstart);
  105. #endif
  106.      if (P<=1) {nextetd = 0; return(TOKENHIT || BITON(TOCC, TOPT));}
  107.      else nextetd = TOKEN.tu.thetd;
  108.      while (STATUS!=RCMISS && STATUS!=RCEND) {
  109.           STATUS = (char)testend(mod, pos, 0, 0);
  110. #ifndef FINAL
  111.           if (ctrace) traceend("ECONTEND", mod, pos, 0, 0, (int)Tstart);
  112. #endif
  113.           nextetd = P<=1 ? 0 : TOKEN.tu.thetd;
  114.           if (STATUS==RCEND)       return(1);
  115.           if (P<=1)                return(TOKENHIT || BITON(TOCC, TOPT));
  116.           if (STATUS==RCMISS) {
  117.                if (BITON(TOCC, TOPT)) nextetd = 0;
  118.                return(0);
  119.           }
  120.           if (!tokenopt(mod, pos)) return(0);
  121.  
  122.           STATUS = RCNREQ;
  123.           if (GTYPE!=TTAND) ++T;   /* T!=GNUM or group would have ended. */
  124.           else T = (char)(((next = (UNS)offbit(H, (int)T, GNUM))!=0) ?
  125.                next : offbit(H, 0, GNUM));
  126.  
  127.           M = G + grpsz(&GHDR, (int)T-1) + 1;
  128. #ifndef FINAL
  129.           if (ctrace) traceend("ECONTNEW", mod, pos, 0, 0, (int)Tstart);
  130. #endif
  131.      }
  132.      if (STATUS==RCMISS) {
  133.           if (BITON(TOCC, TOPT)) nextetd = 0;
  134.           return(0);
  135.      }
  136.      return(1);               /* STATUS==RCEND */
  137. }
  138. /******************************************************************************/
  139. /* NEWTOKEN: Find the next token to test.  Set STATUS to indicate results:
  140.                   RCEND  if element has ended (no more tokens to test);
  141.                   RCREQ  if required new token was found;
  142.                   RCNREQ if non-required new token was found;
  143.                   RCHIT  if a hit token was repeated (now non-required);
  144.               and RCMISS if a new token can't be found because current token
  145.               (which was not hit) was neither unconditionally required nor
  146.               optional.
  147. */
  148. VOID newtoken(mod, pos, statuspt)
  149. struct thdr mod[];            /* Model of current open element. */
  150. struct mpos pos[];            /* Position in open element's model. */
  151. UNCH *statuspt;               /* Token status: RCHIT RCMISS RCEND RCREQ RCNREQ*/
  152. {
  153.      unsigned nextand = 0;    /* Position in AND group of next testable token.*/
  154.      UNCH Psave = 0;          /* For testing whether group ended. */
  155.      int rc = 0;              /* Return code: RCNREQ RCHIT RCMISS RCEND */
  156.      int currhit = (STATUS==RCHIT); /* 1=current GI hit; 0=not. */
  157.  
  158.      /* If the GI was a hit, turn on the hit bit and set the status to
  159.         assume that the token to be tested against the next GI will
  160.         be non-required.  If the current token is repeatable, exit so
  161.         it will stand as the next token to test.
  162.      */
  163.      if (STATUS==RCHIT) {
  164.           BITNON(H, T); STATUS = RCNREQ;
  165.           if (BITON(TOCC, TREP)) return;
  166.      }
  167.      /* At this point, we must determine the next token to test:
  168.         either against the next GI, if this one was a hit, or
  169.         against the same GI if conditions permit a retry.
  170.         To find the next token, we must first end the current group,
  171.         if possible, and any we can that contain it.
  172.         If the outermost group was a hit and is repeatable, or
  173.         if the element has ended, we exit now.
  174.         If it hasn't ended, or was optional and ended with a miss,
  175.         we can retry the GI against the next token.
  176.      */
  177.      if ((STATUS = (char)testend(mod, pos, 1, 1))!=RCNREQ) return;
  178.  
  179.      /* At this point, the "current token" is either the original one,
  180.         or the token for the highest level unhit group that it ended.
  181.         We will retry a missed GI, by testing it against the next
  182.         token, if the current token:
  183.         1. Is optional;
  184.         2. Was hit (i.e., because it is repeatable and was hit by a
  185.            previous GI or because it is a hit group that just ended);
  186.         3. Is in an AND or OR group and is not the last testable token.
  187.  
  188.         It will be the next sequential one (unhit one, in an AND group);
  189.         if there are none left, use the first unhit token in the group.
  190.         In either case, set M to correspond to the new T.
  191.      */
  192.      retest:
  193. #ifndef FINAL
  194.      if (ctrace) traceend("RETEST", mod, pos, (int)nextand, 1, (int)Tstart);
  195. #endif
  196.      if (GTYPE==TTAND) nextand = offbit(H, (int)T, GNUM);
  197.      if ( BITON(TOCC, TOPT)
  198.        || TOKENHIT
  199.        || GTYPE==TTOR              /* T!=GNUM or group would have ended. */
  200.        || nextand ) {
  201.           if (GTYPE!=TTAND) ++T;   /* T!=GNUM or group would have ended. */
  202.           else T = (char)(nextand ? nextand : offbit(H, 0, GNUM));
  203.           M = G + grpsz(&GHDR, (int)T-1) + 1;
  204.           /* If AND group wrapped, it can end if all non-optionals were hit. */
  205.           if (GTYPE==TTAND && T==Tstart && !currhit) {
  206.                Psave = P;
  207.                rc = testend(mod, pos, 0, 1);
  208.                if (Psave!=P) {if ((STATUS = (char)rc)==RCNREQ) goto retest;}
  209.                else STATUS = RCMISS;
  210.           }
  211.      }
  212.      else STATUS = RCMISS;
  213. #ifndef FINAL
  214.      if (ctrace) traceend("NEWTOKEN", mod, pos, (int)nextand, 1, (int)Tstart);
  215. #endif
  216.      return;
  217. }
  218. /******************************************************************************/
  219. /* TESTEND: End the current group, if possible, and any that it is nested in.
  220.             The current token will either be a group header, or some token
  221.             that could not end its group.  Return 1 if the (possibly new)
  222.             current token is repeatable; 0 if it is not.
  223. */
  224. int testend(mod, pos, andoptsw, newtknsw)
  225. struct thdr mod[];            /* Model of current open element. */
  226. struct mpos pos[];            /* Position in open element's model. */
  227. int andoptsw;                 /* 1=test optional AND members; 0=ignore. */
  228. int newtknsw;                 /* 1=new token test; 0=end element test. */
  229. {
  230.      int rc = 0;              /* Return code: RCNREQ RCHIT RCMISS RCEND */
  231.  
  232.      while (!rc) {
  233. #ifndef FINAL
  234.           if (ctrace) traceend("TRACEEND", mod, pos, rc, andoptsw, (int)Tstart);
  235. #endif
  236.           /* TESTMISS:
  237.              If we've hit no tokens yet in the current group, and
  238.              the current token is the last unhit one in the group we can test,
  239.              we will end the group (it may never really have started!)
  240.              because we might be able to try the token that follows it.
  241.              In any group, a token is the last testable unhit token if it
  242.              is the last sequential one, as the GI was already tested against
  243.              the preceding unhit tokens.  In addition,
  244.              in a SEQ group, it is the last testable unhit token if it isn't
  245.              optional, because we can't skip past it to the following ones.
  246.              If we end the group, before popping the level, set M to G, as this
  247.              level`s group header will be the next level's current token.
  248.           */
  249.           if (H==0 && (T==(char)GNUM || GTYPE==TTSEQ && BITOFF(TOCC, TOPT))) {
  250.                M = G; --P; Tstart = T;
  251.                if (P<=1) {
  252.                     if (BITON(TOCC, TOPT) || TOKENHIT) rc = RCEND;
  253.                     else                               rc = RCMISS;
  254.                }
  255.                continue;
  256.           }
  257.           /* TESTHIT:
  258.              See if we've hit all the non-optional tokens in the group.
  259.              If so, pop to the previous level and set the group's hit bit.
  260.              If we were called from NEWTOKEN we are trying to find the token
  261.              to test against the next start-tag, so if the group is repeatable,
  262.              process it again.  (If not, we were called from ECONTEXT and
  263.              are testing whether the element can be ended.)
  264.              Otherwise, if we are at the first level, the element is over.
  265.           */
  266.           if ( GTYPE==TTOR  && TOKENHIT
  267.             || GTYPE==TTSEQ && T==(char)GNUM && (TOKENHIT || BITON(TOCC, TOPT))
  268.             || GTYPE==TTAND && allhit(&GHDR, H, 0, andoptsw) ) {
  269.                M = G; --P; BITNON(H, T); Tstart = T;
  270.                if (newtknsw && BITON(TOCC, TREP)) rc = RCHIT;
  271.                else if (P<=1)                     rc = RCEND;
  272.                /* Else loop to test new outer group. */
  273.           }
  274.           else rc = RCNREQ;   /* No group ended this time, so return. */
  275.      }
  276. #ifndef FINAL
  277.      if (ctrace) traceend("ENDFOUND", mod, pos, rc, andoptsw, (int)Tstart);
  278. #endif
  279.      return(rc);
  280. }
  281. /******************************************************************************/
  282. /* TOKENOPT: Return 1 if current token is contextually optional;
  283.              otherwise, return 0.
  284. */
  285. int tokenopt(mod, pos)
  286. struct thdr mod[];            /* Model of current open element. */
  287. struct mpos pos[];            /* Position in open element's model. */
  288. {
  289. #ifndef FINAL
  290.      if (ctrace) traceend("TOKENOPT", mod, pos, 0, 0, (int)Tstart);
  291. #endif
  292.      return( BITON(TOCC, TOPT)/* Inherently optional. */
  293.           || TOKENHIT         /* Was hit (handles "plus" suffix case). */
  294.           || H==0 && groupopt(mod, pos) );/* In optional group with no hits. */
  295. }
  296. /******************************************************************************/
  297. /* GROUPOPT: Temporarily makes the current group be the current token so that
  298.              TOKENOPT() can be applied to it.  Returns the value returned
  299.              by TOKENOPT.
  300. */
  301. int groupopt(mod, pos)
  302. struct thdr mod[];            /* Model of current open element. */
  303. struct mpos pos[];            /* Position in open element's model. */
  304. {
  305.      UNCH saveM;              /* Save M when testing if group is not required.*/
  306.      int rc;                  /* 1=contextually optional; 0=not. */
  307.  
  308.      if (P==1) return(BITON(GOCC, TOPT) || TOKENHIT);
  309.      saveM = M; M = G; --P;
  310.      rc = tokenopt(mod, pos);
  311.      ++P; G = M; M = saveM;
  312.      return(rc);
  313. }
  314. /******************************************************************************/
  315. /* TOKENREQ: Returns RCREQ if the current token is "contextually required".
  316.              That is, it is not contextually optional and
  317.                  1) it is a member of a "seq" group that is either required
  318.                     or has at least 1 hit token.
  319.                  2) it is a member of an "and" group in which all other
  320.                     tokens were hit.
  321.                           Optional tokens are not counted
  322.                           if GI is ETDCDATA, as we are looking for an
  323.                           omitted start-tag.  Otherwise, they are counted,
  324.                           as the GI might match one of them.
  325.              Returns RCNREQ if the current token is "not required".
  326. */
  327. int tokenreq(gi, mod, pos)
  328. struct etd *gi;               /* ETD of new GI. */
  329. struct thdr mod[];            /* Model of current open element. */
  330. struct mpos pos[];            /* Position in open element's model. */
  331. {
  332. #ifndef FINAL
  333.      if (ctrace) tracegi("TOKENREQ", gi, mod, pos, (int)Tstart);
  334. #endif
  335.      return( tokenopt(mod, pos) ? RCNREQ
  336.             : ( GTYPE==TTSEQ && (H!=0 || groupreq(gi, mod, pos)==RCREQ)
  337.               /*|| GTYPE==TTAND && allhit(&GHDR, H, T, \*gi!=ETDCDATA*\ 1)*/ )
  338.                 ? RCREQ : RCNREQ );
  339. }
  340. /******************************************************************************/
  341. /* GROUPREQ: Temporarily makes the current group be the current token so that
  342.              TOKENREQ() can be applied to it.  Returns the value returned
  343.              by TOKENREQ.
  344. */
  345. int groupreq(gi, mod, pos)
  346. struct etd *gi;               /* ETD of new GI. */
  347. struct thdr mod[];            /* Model of current open element. */
  348. struct mpos pos[];            /* Position in open element's model. */
  349. {
  350.      UNCH saveM;              /* Save M when testing if group is not required.*/
  351.      int rc;                  /* Return code: RCREQ RCNREQ */
  352.  
  353.      if (P==1) return(BITOFF(GOCC, TOPT) ? RCREQ : RCNREQ);
  354.      saveM = M; M = G; --P;
  355.      rc = tokenreq(gi, mod, pos);
  356.      ++P; G = M; M = saveM;
  357.      return(rc);
  358. }
  359. /******************************************************************************/
  360. /* GRPSZ: Returns the number of tokens spanned by a group in the model (M),
  361.           from the group's start (G) to a specified index within the group (T).
  362.           M = 0, plus 1 for each token in the group, plus the size of
  363.           any subgroups (gotten by calling GRPSZ recursively).  On entry,
  364.           M must be equal to G at the current level.
  365. */
  366. int grpsz(g, t)
  367. struct thdr *g;               /* mod[G]: Ptr to group in the model. */
  368. int t;                        /* T: Index of last token in the group. */
  369. {
  370.      struct thdr *p = g;      /* Ptr to current token in the model. */
  371.      int m = 0;               /* Size of group (including nested groups). */
  372.      int i = 0;               /* Number of group members (loop counter). */
  373.      UNS type;                /* Token type (without TOREP bits). */
  374.  
  375.      while (++i<=t) {
  376.           ++p; ++m;
  377.           type = GET(p->ttype, TTMASK);
  378.           if (type==TTOR || type==TTSEQ || type==TTAND) {
  379.                m += grpsz(p, p->tu.tnum);
  380.                p = g+m;
  381.           }
  382.      }
  383.      return(m);
  384. }
  385. /******************************************************************************/
  386. /* ALLHIT: Returns 1 if all hit bits for the specified group are turned on,
  387.            (other than those that correspond to optional tokens if "opt" is
  388.            0) and the "but" bit (all bits if "but" bit is zero).  Otherwise,
  389.            returns 0.  GRPSZ is used to skip past subgroup tokens.
  390. */
  391. int allhit(p, hits, but, opt)
  392. struct thdr *p;               /* mod[G]: Ptr to group in the model. */
  393. long hits;                    /* H: Hit bits to be tested. */
  394. int but;                      /* Index of bit to ignore; 0=test all. */
  395. int opt;                      /* 1=optional tokens must be hit; 0=ignore. */
  396. {
  397.      int b = 0;               /* Index of bit being tested in hits. */
  398.      int e = p->tu.tnum;      /* Ending index (number of bits to test). */
  399.      unsigned type;           /* Token type (without TOREP bits). */
  400.  
  401.      while (++p, ++b<=e) {
  402.           if (BITOFF(hits,1L<<(b-1)) &&(opt || BITOFF(p->ttype,TOPT)) && b!=but)
  403.                return 0;
  404.           if ((type = GET(p->ttype,TTMASK))==TTOR || type==TTSEQ || type==TTAND)
  405.                p += grpsz(p, p->tu.tnum);
  406.      }
  407.      return 1;
  408. }
  409. /******************************************************************************/
  410. /* OFFBIT: Returns the index of the first unset bit after (i.e., not including)
  411.            the caller's "first" bit. If all bits through the
  412.            specified last bit are on, it returns 0.
  413. */
  414. int offbit(bits, first, last)
  415. long bits;                    /* Bits to be tested. */
  416. int first;                    /* Index of first bit to be tested in bits. */
  417. int last;                     /* Index of last bit to be tested in bits. */
  418. {
  419.      while (++first <= last)
  420.           if (BITOFF(bits, 1L<<(first-1))) return first
  421.      ;
  422.      return 0;
  423. }
  424. /******************************************************************************/
  425. #undef GI
  426. #undef NEWGI
  427. #undef STATUS
  428. #undef RCEND
  429. #undef RCREQ
  430. #undef RCMISS
  431. #undef RCHIT
  432. #undef RCMEX
  433. #undef RCHITMEX
  434. #undef RCPEX
  435. #undef RCNREQ
  436. #undef PEX
  437. #undef M
  438. #undef P
  439. #undef G
  440. #undef T
  441. #undef H
  442. #undef GHDR
  443. #undef TOKEN
  444. #undef TTYPE
  445. #undef TOCC
  446. #undef GTYPE
  447. #undef GOCC
  448. #undef GNUM
  449. #undef TOKENHIT
  450. /******************************************************************************/
  451.